package com.levi.linkedlist;

import java.nio.file.attribute.FileTime;

/**
 * @author shentong
 * @date 2021/8/24 20:59
 * @Description 约瑟夫问题 n个人，从第k个开始数，数m个，数到的人出队，从下一个开始数，一次循环，求出队的编号
 */
public class Josephu {
    public static void main(String[] args) {
        SingleCircleLinkedList circleLinkedList = new SingleCircleLinkedList();
        System.out.println("往单向环形链表中添加节点：----------");
        circleLinkedList.add(25);
        System.out.println("遍历单向唤醒列表:--------------");
        circleLinkedList.list();
        System.out.println("约瑟夫问题开始:---------------");
        circleLinkedList.josephu(25,1,2);
    }
}

/**
 * 单向环形链表
 */
class SingleCircleLinkedList{
    //创建一个first节点
    private Boy first = null;
    /**
     *
     * @param num
     */
    public void add(Integer num) {
        if (num < 1) {
            throw new RuntimeException("num不能小于1");
        }
        //first不能动，所以需要一个辅助节点，帮助遍历
        Boy cur = null;

        for (int i = 1; i <= num; i++) {
            //如果是第一个节点，就把first的next指向自己，形成一个环形
            var boy = new Boy(i);
            if (i == 1) {
                first = boy;
                //把first的next指向自己，形成环状
                first.setNext(first);
                //让cur指向first
                cur = first;
            }else{
                //让cur的next指向新节点
                cur.setNext(boy);
                //让新节点next指向第一个节点，形成闭环
                boy.setNext(first);
                //让cur后移
                cur = boy;
            }
        }
    }

    /**
     * 遍历单向环形链表
     */
    public void list() {
        if (first == null) {
            throw new RuntimeException("链表为空");
        }
        var temp = first;
        while (first.getNext() != first ) {
            System.out.println(temp);
            if (temp.getNext()==first){
                break;
            }
            temp = temp.getNext();
        }
    }

    /**
     * 约瑟夫问题
     * @param n  一共有多少个人
     * @param k  从第几个开始数
     * @param m  数多少下
     *       思路如下:
     *           1.因为是单向链表，所以要创建一个辅助节点temp帮助删除节点，temp初始在链表的最后一个节点
     *           2.因为要从第k个节点开始数，所以temp和first都要往后先移动(k-1)下，for循环实现移动
     *           3.移动的时候first和temp都往后移动(m-1),因为自己也要数一下，for循环实现移动
     *           4.移动之后此时要删除的节点就是first节点本身，将first打印出来
     *           5.删除first节点，将first指向first的下一个节点，将temp的下一个节点指向first,即[first =  first.next,temp.next = first]
     */
    public void josephu(Integer n,Integer k,Integer m) {
        //判断参数合法性
        if (k < 1 || m > n || n <1) {
            throw new RuntimeException("参数有误");
        }
        //先创建一个辅助节点temp，让指向链表的最后一个节点(循环遍历实现),退出while循环时temp就是最后一个节点
        Boy temp = first;
        while (temp.getNext()!=first){
            temp = temp.getNext();
        }
        //让first和temp移动k-1下(从第k个开始数)
        for (int i = 0; i < k - 1; i++) {
            temp = temp.getNext();
            first = first.getNext();
        }
        //如果temp和first相等，说明链表中只剩下最后一个节点，这时候退出循环,不然的话继续数
        while (temp != first) {
            //让temp和first继续往后移动m-1下，
            for (int i = 0; i < m - 1; i++) {
                temp = temp.getNext();
                first = first.getNext();
            }
            //移动之后这时候要删除的节点就是first节点,将其打印出来
            System.out.printf("出圈的节点编号是:%d\n", first.getNo());
            //打印之后删除该节点,first指向first的下一个节点，temp的next指向现在的first
            first = first.getNext();
            temp.setNext(first);
        }

        System.out.printf("最后剩下的节点编号是%d\n",first.getNo());
    }
}

class Boy{
    private Integer no;
    private Boy next;

    public Boy(Integer no) {
        this.no = no;
    }

    public Integer getNo() {
        return no;
    }

    public void setNo(Integer no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}